Алгоритм нахождения решений произвольной системы линейных уравнений (метод Гаусса)

Пусть дана система

линейных уравнений с

неизвестными

. Требуется найти ее общее решение, если она совместна, или установить ее несовместность. Метод, который будет изложен в этом разделе, близок к методу вычисления определителя 5.1.с и к методу нахождения ранга матрицы (раздел 5.8). Предлагаемый алгоритм называется методом Гаусса или методом последовательного исключения неизвестных.

Выпишем расширенную матрицу системы

$\displaystyle A^*=\left(\begin{array}{ccccc}a_{11}&a_{12}&\dots&a_{1n}&b_1\\ ... ...{2n}&b_2\\ \hdotsfor{5}\\ a_{m1}&a_{m2}&\dots&a_{mn}&b_m\end{array}\right).$

Назовем элементарными операциями следующие действия с матрицами:

перестановка строк;
умножение строки на число, отличное от нуля;
сложение строки с другой строкой, умноженной на число.

Отметим, что при решении системы уравнений, в отличие от вычисления определителя и нахождения ранга, нельзя оперировать со столбцами.

Читатель легко проверит, что если по матрице, полученной из выполнением элементарной операции, восстановить систему уравнений, то новая система будет равносильна исходной.

Цель алгоритма -- с помощью применения последовательности элементарных операций к матрице добиться, чтобы каждая строка, кроме, быть может, первой, начиналась с нулей, и число нулей до первого ненулевого элемента в каждой следующей строке было больше, чем в предыдущей.

Шаг алгоритма заключается в следующем. Находим первый ненулевой столбец в матрице . Пусть это будет столбец с номером . Находим в нем ненулевой элемент и строку с этим элементом меняем местами с первой строкой. Чтобы не нагромождать дополнительных обозначений, будем считать, что такая смена строк в матрице уже произведена, то есть ${a_{1i}\ne0}$ . Тогда ко второй строке прибавим первую, умноженную на число $\left(-\dfrac{a_{2i}}{a_{1i}}\right)$ , к третьей строке прибавим первую, умноженную на число $\left(-\dfrac{a_{3i}}{a_{1i}}\right)$ , и т.д. В результате получим матрицу

$\displaystyle A^*_1=\left(\begin{array}{cccccccc}0&\dots&0&a_{1i}&a_{1i+1}&\dot... ...\\ 0&\dots&0&0&a_{mi+1}^{(1)}&\dots&a_{mn}^{(1)}&b_m^{(1)}\end{array}\right).$

(Первые нулевые столбцы, как правило, отсутствуют.)

Если в матрице встретилась строка с номером , в которой все элементы $a_{kj}^{(1)}$ равны нулю, а ${b_k^{(1)}\ne0}$ , то выполнение алгоритма останавливаем и делаем вывод, что система несовместна. Действительно, восстанавливая систему уравнений по расширенной матрице, получим, что -ое уравнение будет иметь вид

$\displaystyle 0\cdot x_1+0\cdot x_2+\ldots0\cdot x_n=b_k^{(1)}.$

Этому уравнению не удовлетворяет ни один набор чисел ${x_1,x_2,\dots,x_k}$ .

Матрицу можно записать в виде

$\displaystyle A^*_1=\left(\begin{array}{ccc}{\begin{array}{ccc}0&\dots&0\end{ar... ...begin{array}{c}0\\ \vdots\\ 0\end{array}}&\mbox{\Huge\it B*}\end{array}\right),$

где

$\displaystyle B^*=\left(\begin{array}{ccccc} a_{2i+1}^{(1)}&a_{2i+2}^{(1)}&\do... ... a_{mi+1}^{(1)}&a_{mi+2}^{(1)}&\dots&a_{mn}^{(1)}&b_m^{(1)}\end{array}\right).$

По отношению к матрице

выполняем описанный шаг алгоритма. Получаем матрицу

$\displaystyle B_1^*=\left(\begin{array}{cccccccc} 0&\dots&0&a_{2j}^{(2)}&a_{2j... ...\\ 0&\dots&0&0&a_{mj+1}^{(2)}&\dots&a_{mn}^{(2)}&b_m^{(2)}\end{array}\right),$

где

, $a_{2j}^{(2)}\ne0$ . Эту матрицу снова можно записать в виде

$\displaystyle B^*_1=\left(\begin{array}{ccc}{\begin{array}{ccc}0&\dots&0\end{ar... ...begin{array}{c}0\\ \vdots\\ 0\end{array}}&\mbox{\Huge\it C*}\end{array}\right),$

и к матрице

снова применим описанный выше шаг алгоритма.

Процесс останавливается, если после выполнения очередного шага новая уменьшенная матрица состоит из одних нулей или если исчерпаны все строки. Заметим, что заключение о несовместности системы могло остановить процесс и ранее.

Если бы мы не уменьшали матрицу, то в итоге пришли бы к матрице вида

$\displaystyle \tilde A^*=\left(\begin{array}{ccccccccccccc} 0&\dots&0&a_{1i}^{... ... \hdotsfor{13}\\ 0&\dots&0&0&\dots&0&0&\dots&0&0&\dots&0&0\end{array}\right).$

Далее выполняется так называемый обратный ход метода Гаусса. По матрице $\tilde A^*$ составляем систему уравнений. В левой части оставляем неизвестные с номерами, соответствующими первым ненулевым элементам в каждой строке, то есть ${x_i,\,x_j,\,\dots,x_r}$ . Заметим, что ${r={\rm Rg}A}$ . Остальные неизвестные переносим в правую часть. Считая неизвестные в правой части некоторыми фиксированными величинами, несложно выразить через них неизвестные левой части.

Теперь, придавая неизвестным в правой части произвольные значения и вычисляя значения переменных левой части, мы будем находить различные решения исходной системы . Чтобы записать общее решение, нужно неизвестные в правой части обозначить в каком-либо порядке буквами ${C_1,\,C_2,\dots,C_{n-r}}$ , включая и те неизвестные, которые явно не выписаны в правой части из-за нулевых коэффициентов, и тогда столбец неизвестных можно записать в виде столбца, где каждый элемент будет линейной комбинацией произвольных величин ${C_1,\,C_2,\dots,C_{n-r}}$ (в частности, просто произвольной величиной ). Эта запись и будет общим решением системы.

Если система была однородной, то получим общее решение однородной системы. Коэффициенты при , взятые в каждом элементе столбца общего решения, составят первое решение из фундаментальной системы решений, коэффициенты при -- второе решение и т.д.

Фундаментальную систему решений однородной системы можно получить и другим способом. Для этого одному переменному, перенесенному в правую часть, нужно присвоить значение 1, а остальным -- нули. Вычислив значения переменных в левой части, получим одно решение из фундаментальной системы. Присвоив другому переменному в правой части значение 1, а остальным -- нули, получим второе решение из фундаментальной системы и т.д.

Замечание 15.4 У читателя может возникнуть вопрос: "Зачем рассматривать случай, когда некоторые столбцы матрицы

нулевые? Ведь в этом случае соответствующие им переменные в системе уравнений в явном виде отсутствуют." Но дело том, что в некоторых задачах, например, при нахождении собственных чисел матрицы, такие системы возникают, и игнорировать отсутствующие переменные нельзя, так как при этом происходит потеря важных для задачи решений.

Пример 15.2 Найдите общее решение системы уравнений

$\displaystyle \left\{\begin{array}{l}2x_2+x_3-2x_4+4x_5+x_6=2,\\ 8x_2+4x_3-8x_4+13x_5+2x_6=14,\\ 6x_2+3x_3-6x_4+6x_5-x_6=18,\end{array}\right.$

где неизвестными являются $x_1,\ldots,x_6$ .

Решение. Выпишем расширенную матрицу системы

$\displaystyle A^*=\left(\begin{array}{rrrrrrr}0&2&1&-2&4&1&2\\ 0&8&4&-8&13&2&14\\ 0&6&3&-6&6&-1&18\end{array}\right).$

Прибавим ко второй строке первую, умноженную на число ${\left(-\dfrac82\right)=-4}$ , к третьей строке прибавим первую, умноженную на ${\left(-\dfrac62\right)=-3}$ . В результате получим

$\displaystyle A^*_1=\left(\begin{array}{rrrrrrr}0&2&1&-2&4&1&2\\ 0&0&0&0&-3&-2&6\\ 0&0&0&0&-6&-4&12\end{array}\right).$

Прибавим к третьей строке вторую, умноженную на число ${\left(-\dfrac{-6}{-3}\right)=-2}$ . Получим

$\displaystyle A^*_1=\left(\begin{array}{rrrrrrr}0&2&1&-2&4&1&2\\ 0&0&0&0&-3&-2&6\\ 0&0&0&0&0&0&0\end{array}\right).$

Прямой ход метода Гаусса закончен. Выписываем по матрице

систему уравнений

$\displaystyle \left\{\begin{array}{r@{\;=\;}l} 2x_2+x_3-2x_4+4x_5+x_6&2,\\ -3x_5-2x_6&6.\end{array}\right.$

Переносим в правую часть неизвестные ${x_1,\,x_3,\,x_4,\,x_6}$ (неизвестное

реально в ней присутствовать не будет, коэффициент перед ним равен нулю). Получаем

$\displaystyle \left\{\begin{array}{r@{\;=\;}l} 2x_2+4x_5&2-x_3+2x_4-x_6,\\ -3x_5&6+2x_6.\end{array} \right.$

Пусть ${x_1=C_1}$ , ${x_3=C_2}$ , ${x_4=C_3}$ , ${x_6=C_4}$ . Из уравнений находим:

$\displaystyle x_5=-2-\frac23C_4,$

$\displaystyle x_2=-2x_5+1-\frac12 C_2+C_3-\frac12C_4=4+\frac43C_4+1-\frac12C_2+C_3-\frac12 C_4=5-\frac12C_2+C_3+ \frac56C_4.$

Ответ: ${x_1=C_1}$ , ${x_2=5-\dfrac12C_2+C_3+\dfrac56C_4}$ , ${x_3=C_2}$ , ${x_4=C_3}$ , ${x_5=-2-\dfrac23C_4}$ , ${x_6=C_4}$ , где , , , -- произвольные числа.

Замечание 15.5 В процессе решения можно также установить, какие ранги у матриц

и где расположены их базисные миноры. В предыдущем примере ${{\rm Rg}A={\rm Rg}A^*=2}$ , базисный минор расположен в строках с номерами 1, 2, столбцах с номерами 2, 5.

Пример 15.3 Найдите общее решение системы уравнений

$\displaystyle \left\{\begin{array}{l}x_1+x_2+2x_3-x_4=3,\\ 2x_1-x_2+3x_3+4x_4=-1,\\ 4x_1+x_2+7x_3+2x_4=6,\\ 5x_1-x_2+3x_3+2x_4=-3.\end{array}\right.$

Решение. Запишем расширенную матрицу системы:

$\displaystyle A^*=\left(\begin{array}{rrrrr} 1&1&2&-1&3\\ 2&-1&3&4&-1\\ 4&1&7&2&6\\ 5&-1&3&2&-3\end{array}\right).$

Ко второй строке прибавим первую, умноженную на

, к третьей строке прибавим первую, умноженную на

, к четвертой строке прибавим первую, умноженную на

$\displaystyle A^*_1=\left(\begin{array}{rrrrr} 1&1&2&-1&3\\ 0&-3&-1&6&-7\\ 0&-3&-1&6&-6\\ 0&-6&-7&7&-18\end{array}\right).$

Вторую строку, умноженную на

, прибавим к третьей:

$\displaystyle A^*_2=\left(\begin{array}{rrrrr} 1&1&2&-1&3\\ 0&-3&-1&6&-7\\ 0&0&0&0&1\\ 0&-6&-7&7&-18\end{array}\right).$

В третьей строке все элементы $a_{3j}^{(2)}$ равны нулю, а элемент ${b_3^{(2)}\ne0}$ . Значит, система несовместна.

Ответ: Система несовместна.

Пример 15.4 Решите систему

$\displaystyle \left\{\begin{array}{l}2x_1-x_2+3x_3-x_4=1,\\ 3x_1+2x_2-x_3+x_4=2,\\ 2x_1+x_2+2x_3-3x_4=1,\\ 4x_1-2x_2-x_3-3x_4=2.\end{array}\right.$

Решение. Имеем:

$\displaystyle A^*=\left(\begin{array}{rrrrr} 2&-1&3&-1&1\\ 3&2&-1&1&2\\ 2&1&2&-3&1\\ 4&-2&-1&-3&2\end{array}\right).$

Первую строку, умноженную на числа $\left(-\frac32\right)$ ,

, прибавим соответственно ко второй, третьей и четвертой строкам:

$\displaystyle A^*_1=\left(\begin{array}{rrrrr} 2&-1&3&-1&1\\ 0&\vphantom{\dfrac... ...&-\frac{11}2& \frac52&\frac12\\ 0&2&-1&-2&0\\ 0&0&-7&-1&0\end{array}\right).$

К третьей строке прибавим вторую, умноженную на $\left(-\frac47\right)$ . Получим

$\displaystyle A^*_2=\left(\begin{array}{rrrrr} 2&-1&3&-1&1\\ 0&\vphantom{\dfrac... ...tom{\dfrac11}\frac{15}7&-\frac{24}7&-\frac27\\ 0&0&-7&-1&0\end{array}\right).$

К четвертой строке прибавим третью, умноженную на $\frac{49}{15}$ :

$\displaystyle A^*_3=\left(\begin{array}{rrrrr} 2&-1&3&-1&1\\ 0&\vphantom{\dfrac... ...ac27\\ 0&0&0&\vphantom{\dfrac11}-\frac{61}5&-\frac{14}{15}\end{array}\right).$

Выписываем по матрице

систему уравнений:

$\displaystyle \left\{\begin{array}{r@{\,\,=\,}r}2x_1-x_2+3x_3-x_4&1,\\ \vphan... ...frac27,\\ \vphantom{\dfrac11}-\frac{61}5x_4&-\frac{14}{15}.\end{array}\right.$

Находим последовательно значения неизвестных:

$\displaystyle x_4=\frac{14}{183},\quad x_3=\left(-\frac27+\frac{24}7x_4\right):... ... =\left(-\frac27+\frac{24}7\cdot\frac{14}{183}\right):\frac{15}7=-\frac2{183},$

$\displaystyle x_2=\left(\frac12+\frac{11}2x_3-\frac52x_4\right):\frac72= \left... ...1}2\cdot\frac2{183}-\frac52\cdot\frac{14}{183} \right):\frac72=\frac{13}{183},$

$\displaystyle x_1=(1+x_2-3x_3+x_4):2=\left(1+\frac{13}{183}+\frac6{183}+\frac{14}{183} \right):2=\frac{108}{183}.$

Ответ: $x_1=\frac{108}{183},\quad x_2=\frac{13}{183},\quad x_3=-\frac2{183},\quad x_4=\frac{14}{183}$ .

Замечание 15.6 Так же, как и при решении системы уравнений по правилу Крамера, при использовании метода Гаусса приходится выполнять большой объем вычислительной работы. Из-за этого вполне возможно, что будет допущена какая-либо ошибка в вычислениях. Поэтому желательно после решения системы выполнить проверку, то есть подставить полученные значения неизвестных в уравнения системы. Для выполнения полной проверки подстановку нужно произвести во все уравнения системы. Если же по каким-то причинам это не выполнимо, то можно подставить найденные значения в одно уравнение. В отличие от правила Крамера в методе Гаусса эту подстановку нужно производить в ПОСЛЕДНЕЕ уравнение исходной системы. При наличии в этом уравнении всех неизвестных эта подстановка почти всегда покажет наличие ошибки, если таковая была допущена.

Пример 15.5 Найдите фундаментальную систему решений и общее решение однородной системы линейных уравнений:

$\displaystyle \left\{\begin{array}{l}x_1+x_2-x_3+2x_4-x_5=0,\\ 2x_1-x_2-x_3-x_4... ... -5x_1+7x_2+x_3+10x_4-11x_5=0,\\ -x_1+5x_2-x_3+8x_4-7x_5=0.\end{array}\right.$

Решение. Составляем расширенную матрицу системы:

$\displaystyle A^*=\left(\begin{array}{rrrrrr} 1&1&-1&2&-1&0\\ 2&-1&-1&-1&2&0\\ -5&7&1&10&-11&0\\ -1&5&-1&8&-7&0\end{array}\right).$

Умножим первую строку последовательно на

, 5 и 1 и прибавим соответственно ко второй, третьей и четвертой строкам. Получим матрицу

$\displaystyle A^*_1=\left(\begin{array}{rrrrrr} 1&1&-1&2&-1&0\\ 0&-3&1&-5&4&0\\ 0&12&-4&20&-16&0\\ 0&6&-2&10&-8&0\end{array}\right).$

Вторую строку умножим последовательно на числа 4 и 2 и прибавим соответственно к третьей и четвертой строкам. Получим матрицу

$\displaystyle A^*_2=\left(\begin{array}{rrrrrr} 1&1&-1&2&-1&0\\ 0&-3&1&-5&4&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\end{array}\right).$

Прямой ход метода Гаусса закончен. У полученной матрицы легко определить ранг, ее базисный минор $\left\vert\begin{array}{rr}1&1\\ 0&-3\end{array}\right\vert$ . Отсюда следует, что ${{\rm Rg}A={\rm Rg}A^*_2=2}$ . По теореме 15.3 число решений в фундаментальной системе равно разности между числом неизвестных и рангом матрицы, в нашем случае фундаментальная система состоит из трех решений.

Переходим к системе уравнений

$\displaystyle \left\{\begin{array}{r@{\;=\;}l}x_1+x_2-x_3+2x_4-x_5&0,\\ -3x_2+x_3-5x_4+4x_5&0.\end{array}\right.$

Неизвестные

оставляем в левой части, остальные переносим в правую часть:

$\displaystyle \left\{\begin{array}{r@{\;=\;}l}x_1+x_2&x_3-2x_4+x_5,\\ -3x_2&-x_3+5x_4-4x_5.\end{array}\right.$

Положим ${x_3=1}$ , ${x_4=x_5=0}$ . Получим ${x_2=\frac13}$ , ${x_1=\frac23}$ . Первое решение из фундаментальной системы: ${x^{(1)}=\left(\begin{array}{r}\vphantom{\dfrac11}\frac23\\ \vphantom{\dfrac11}\frac13\\ 1\\ 0\\ 0\end{array}\right)}$ .

Положим ${x_3=x_5=0}$ , ${x_4=1}$ . Получим ${x_2=-\frac53}$ , ${x_1=-\frac13}$ . Второе решение из фундаментальной системы решений: ${x^{(2)}=\left(\begin{array}{r}\vphantom{\dfrac11}-\frac13\\ \vphantom{\dfrac11}-\frac53\\ 0\\ 1\\ 0\end{array}\right)}$ .

Положим ${x_3=x_4=0}$ , ${x_5=1}$ . Получим ${x_2=\frac43}$ , ${x_1=-\frac13}$ . Третье решение из фундаментальной системы решений: ${x^{(3)}=\left(\begin{array}{r}\vphantom{\dfrac11}-\frac13\\ \vphantom{\dfrac11}\frac43\\ 0\\ 0\\ 1\end{array}\right)}$ . Фундаментальная система решений найдена. Общее решение имеет вид

$\displaystyle x=C_1x^{(1)}+C_2x^{(2)}+C_3x^{(3)}.$

Ответ: Фундаментальная система решений:
${x^{(1)}=\left(\begin{array}{r}\vphantom{\dfrac11}\frac23\\ \vphantom{\dfrac11}\frac13\\ 1\\ 0\\ 0\end{array}\right)}$ , ${x^{(2)}=\left(\begin{array}{r}\vphantom{\dfrac11}-\frac13\\ \vphantom{\dfrac11}-\frac53\\ 0\\ 1\\ 0\end{array}\right)}$ , ${x^{(3)}=\left(\begin{array}{r}\vphantom{\dfrac11}-\frac13\\ \vphantom{\dfrac11}\frac43\\ 0\\ 0\\ 1\end{array}\right)}$ , общее решение: ${\left(\begin{array}{c}x_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)=C_1 \lef... ...frac11}-\frac13\\ \vphantom {\dfrac11}\frac43\\ 0\\ 0\\ 1\end{array}\right)}$ .

Замечание 15.7 Если решения, составляющие фундаментальную систему, умножить на любые ненулевые числа, то вновь полученные решения снова будут образовывать фундаментальную систему. Поэтому в предыдущем примере фундаментальную систему образуют и такие решения:
$\hat x^{(1)}=\left(\begin{array}{r}2\\ 1\\ 3\\ 0\\ 0\end{array}\right)$ , $\hat x^{(2)}=\left(\begin{array}{r}-1\\ -5\\ 0\\ 3\\ 0\end{array}\right)$ , $\hat x^{(3)}=\left(\begin{array}{r}-1\\ 4\\ 0\\ 0\\ 3\end{array}\right)$ . Общее решение можно записать так: $\left(\begin{array}{c}x_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right)= C_1\left... ...d{array}\right)+C_3 \left(\begin{array}{r}-1\\ 4\\ 0\\ 0\\ 3\end{array}\right)$ .